//
//  main.cpp
//  JZ39 数组中出现次数超过一半的数字
//
//  Created by Yan Zihao on 2024/10/8.
//

#include <iostream>
#include<vector>
using namespace std;
class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型vector
     * @return int整型
     */
    int MoreThanHalfNum_Solution(vector<int>& numbers)
    {
/*        int arr[10] = {0};
        int size = numbers.size();
        for(int i = 0;i < size;i++)
        {
            arr[numbers[i]]++;
        }
        for(int j = 0;j < 10;j++)
        {
            if(arr[j] >= size/2)
            {
                return j;
            }
        }
        return -1;
 */
        int candidate = numbers[0]; // 初始候选人，默认是第一个数字
        int count = 1;              // 计数器，记录候选人出现的次数
        
        // 1. 找到可能的多数元素
        for(int i = 1; i < numbers.size(); i++)
        { // 从第二个数字开始遍历
            if(count == 0)
            {       // 如果计数器归零，重新选择候选人
                candidate = numbers[i];
                count = 1;
            }
            else if(numbers[i] == candidate)
            { // 如果当前数字和候选人相同，计数器加1
                count++;
            }
            else
            {               // 如果不同，计数器减1
                count--;
            }
        }
        
        // 2. 验证候选人是否确实是多数元素
        count = 0; // 重新计算候选人出现的次数
        for(int i = 0; i < numbers.size(); i++)
        {
            if(numbers[i] == candidate)
            {
                count++;
            }
        }
        
        if(count > numbers.size() / 2)
        { // 如果候选人出现的次数超过一半，返回候选人
            return candidate;
        } else
        { // 否则返回 -1
            return -1;
        }
    }
};
